package demo1;
import java.util.*;
public class Solution {
    //1.最长公共前缀(暴力，但是击败60%)
    public String longestCommonPrefix(String[] strs) {
        String cmp = strs[0];//用来比较的字符串
        StringBuilder ret = new StringBuilder();//返回相同的前缀
        for(int i = 0; i < cmp.length(); i++){
            int ans = 0;
            boolean flag = true;
            for(int j = 1; j < strs.length; j++){
                if(i >= strs[j].length()) {
                    return ret.toString();
                }
                if(strs[j].charAt(i) != cmp.charAt(i)){
                    flag = false;
                    return ret.toString();
                }
            }
            if(flag){
                ret.append(cmp.charAt(i));
            }
        }
        return ret.toString();
    }
    //2.罗马数字转整数(switch翻译)
    public int romanToInt(String s) {
        int sum = 0;
        //从后向前遍历
        for(int i = s.length() - 1; i >= 0; i--){
            if(i < s.length() - 1 && getNum(s.charAt(i)) < getNum(s.charAt(i + 1))){
                sum += -getNum(s.charAt(i));
            }else{
                sum += getNum(s.charAt(i));
            }
        }
        return sum;
    }
    //对应表
    private int getNum(char ch){
        switch(ch){
            case 'I': return 1;
            case 'V': return 5;
            case 'X': return 10;
            case 'L': return 50;
            case 'C': return 100;
            case 'D': return 500;
            case 'M': return 1000;
        }
        return -1;
    }
    //3.最后一个单词的长度
    public int lengthOfLastWord(String s) {
        int len = s.length();
        int count = 0;
        //从后向前遍历，遍历完第一个单词结束
        int end = len - 1;
        //去除尾部的空格
        if(s.charAt(len - 1) == ' '){
            while(end >= 0 && s.charAt(end) == ' '){
                end--;
            }
        }
        //找前一个单词
        while(end >= 0 && s.charAt(end) != ' '){
            count++;
            end--;
        }
        return count;
    }
    //4.反转字符串(边界指针交换)
    public void reverseString(char[] s) {
        int left = 0;
        int right = s.length - 1;
        while(left < right){
            char tmp = s[right];
            s[right] = s[left];
            s[left] = tmp;
            left++;
            right--;
        }
    }
    //剑指 Offer 05. 替换空格
    public String replaceSpace(String s) {
        StringBuilder ret = new StringBuilder();
        for(int i = 0; i < s.length(); i++){
            char ch = s.charAt(i);
            if(ch != ' '){
                ret.append(ch);
            }else{
                ret.append("%20");
            }
        }
        return ret.toString();
    }
    //6.有效的字母异位词(哈希表)
    public boolean isAnagram(String s, String t) {
        //哈希表
        Map<Character, Integer> hash = new HashMap<>();
        //将s放入hash表中
        for(int i = 0; i < s.length(); i++){
            char ch = s.charAt(i);
            if(!hash.containsKey(ch)){
                hash.put(ch, 1);
            }else{
                hash.put(ch, hash.get(ch) + 1);
            }
        }
        //对比t，做减法
        for(int i = 0; i < t.length(); i++){
            char ch = t.charAt(i);
            if(hash.containsKey(ch)){
                hash.put(ch, hash.get(ch) - 1);
            }else{
                return false;
            }
        }
        //不等于0的就是无效
        for(char ch : hash.keySet()){
            if(hash.get(ch) != 0){
                return false;
            }
        }
        return true;
    }
    //7.剑指 Offer 58 - II. 左旋转字符串(转移法)
/*    public String reverseLeftWords(String s, int n) {
        int len = s.length();
        while(n > len){
            return s;
        }
        StringBuilder ret = new StringBuilder();
        for(int i = n; i < s.length(); i++){
            ret.append(s.charAt(i));
        }
        //在将前两个放入
        for(int i = 0; i < n; i++){
            ret.append(s.charAt(i));
        }
        return ret.toString();
    }*/
    //7.剑指 Offer 58 - II. 左旋转字符串(逆置法)
    public String reverseLeftWords(String s, int n) {
        int len = s.length();
        if(n > len){
            return s;
        }
        char[] ret = s.toCharArray();
        //逆序法
        reverse(ret, 0, n - 1);
        reverse(ret, n, len - 1);
        reverse(ret, 0, len - 1);
        return String.valueOf(ret);
    }
/*    public void reverse(char[] ret, int start, int end){
        while(start < end){
            char tmp = ret[start];
            ret[start] = ret[end];
            ret[end] = tmp;
            start++;
            end--;
        }
    }*/
    //8.二进制求和(模拟进位)
    public String addBinary(String a, String b) {
        StringBuilder ret = new StringBuilder();
        int add = 0;//进位
        for(int i = a.length() - 1, j = b.length() - 1; i >= 0 || j >= 0; i--, j--){
            int sum = add;//来自低位的进位
            sum += (i >= 0 ? a.charAt(i) - '0' : 0);//i > 0返回当前数字，小于零向高位补零(1也可以写成01)
            sum += (j >= 0 ? b.charAt(j) - '0' : 0);//同理
            ret.append(sum % 2);
            add = sum / 2;//没有大于等于2，就没有进位
        }
        //处理进位
        if(add == 1){
            ret.append('1');
        }
        //反转字符串
        return ret.reverse().toString();
    }
    //9.判断子序列(双指针法)
    public boolean isSubsequence(String s, String t) {
        int lenS = s.length();
        int lenT = t.length();
        //双指针
        int leftS = 0;
        int leftT = 0;
        while(leftS < lenS && leftT < lenT){
            if(s.charAt(leftS) == t.charAt(leftT)){//相等，两个都向后走
                leftS++;
                leftT++;
            }else{//不相等，让长的向后走
                leftT++;
            }
        }
        //如果短的没有超出范围，说明存在找不到的
        if(leftS < lenS){
            return false;
        }else{
            return true;
        }
    }
    //10.反转字符串中的单词 III(分割法)
    public String reverseWords(String s) {
        StringBuilder ret = new StringBuilder();
        //切割字符串
        String[] strArr = s.split(" ");
        for(int i = 0; i < strArr.length; i++){
            char[] ch = strArr[i].toCharArray();
            reverse(ch, 0, ch.length - 1);
            ret.append(ch);
            if(i < strArr.length - 1){
                ret.append(" ");
            }
        }
        return ret.toString();
    }
    //逆序
    private void reverse(char[] ch, int start, int end){
        while(start < end){
            char tmp = ch[start];
            ch[start] = ch[end];
            ch[end] = tmp;
            start++;
            end--;
        }
    }
}
